package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月10日
*时间：上午11:03:43
*/
public class Q516 {
    /**
     * @param costs n x k cost matrix
     * @return an integer, the minimum cost to paint all houses
     */
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length <= 0) {
            return 0;
        }
        int length = costs.length;
        int n = costs[0].length;
        int dp[][] = new int[length][n];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    dp[i][j] = costs[i][j];
                } else {
                    dp[i][j] = min(dp[i - 1], j) + costs[i][j];
                }
            }
        }
        return min(dp[length - 1], -1);
    }

    private int min(int[] a, int j) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (i != j) {
                if (min > a[i]) {
                    min = a[i];
                }
            }
        }
        return min;
    }

    @Test
    public void testA() {
        int[][] costs = { { 7, 14, 9, 12 }, { 10, 14, 2, 9 }, { 5, 9, 7, 9 }, { 5, 6, 17, 6 }, { 9, 14, 9, 17 }, { 1, 17, 17, 5 }, { 15, 16, 11, 15 },
                { 5, 19, 15, 1 }, { 19, 1, 17, 6 }, { 9, 8, 9, 6 }, { 8, 11, 6, 1 }, { 11, 7, 18, 8 }, { 4, 5, 18, 7 }, { 15, 18, 19, 12 }, { 1, 12, 13, 10 },
                { 18, 3, 14, 17 } };
        System.out.println(minCostII(costs));
    }
}
